11512 - GATTACA/Gattaca_Tries.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 class Node{
   5         int info;
   6         Node sons[];
   7
   8         Node(){
   9                 info = 0;
  10                 sons = new Node[4];
  11         }
  12 }
  13 public class Gattaca_Tries {
  14
  15         public static String letras = "ACGT";
  16         public static void main(String[] args) throws Exception {
  17                 BufferedReader br=new BufferedReader(new FileReader("gattaca.in"));
  18                 for (int T=Integer.parseInt(br.readLine()),c=0; c<T; c++) {
  19                         String s=br.readLine();
  20                         int n=s.length(), rep=0;
  21                         String ans = "";
  22
  23                         Node root = new Node();
  24
  25                         for (int i=0; i<n; ++i){
  26                                 Node foot = root; //Tells me where i'm standing.
  27                                 String so_far = "";
  28                                 for (int j=i; j<n; ++j){
  29                                         //System.out.println("i " + i + " j " + j);
  30
  31                                         so_far = s.substring(i, j);
  32                                         int v = letras.indexOf(s.charAt(j));
  33                                         if (foot.sons[v] == null) foot.sons[v] = new Node();
  34                                         foot = foot.sons[v];
  35                                         int t = ++foot.info;
  36                                         if (t > 1 && (so_far.length() > ans.length() || (so_far.length() == ans.length() && so_far.compareTo(ans) < 0))){
  37                                                 ans = so_far;
  38                                                 rep = t;
  39                                         }
  40                                 }
  41                         }
  42                         System.out.println(ans.length() == 0 ?"No repetitions found!":(ans + " " + rep));
  43                 }
  44                 br.close();
  45         }
  46 }